// 力扣44. 通配符匹配
import java.util.*;

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        // 创建dp数组，dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 空字符串与空模式匹配
        dp[0][0] = true;

        // 处理模式以*开头的情况，*可以匹配空字符串
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sc = s.charAt(i - 1);
                char pc = p.charAt(j - 1);

                if (sc == pc || pc == '?') {
                    // 当前字符匹配，状态由前一个字符决定
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    // *可以匹配空字符(dp[i][j-1])或多个字符(dp[i-1][j])
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
                // 其他情况不匹配，保持默认false
            }
        }

        return dp[m][n];
    }
}




// 力扣60. 排列序列
class Solution1 {
    public String getPermutation(int n, int k) {
        // 计算阶乘，用于确定每一位数字
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        // 存储可用数字
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        // 转换为0基索引，方便计算
        k--;

        StringBuilder result = new StringBuilder();

        // 确定每一位的数字
        for (int i = 1; i <= n; i++) {
            // 计算当前位置有多少种排列
            int count = factorial[n - i];
            // 确定当前位应该选择第几个数字
            int index = k / count;

            // 选择数字并添加到结果
            result.append(numbers.get(index));
            // 从可用数字中移除已选择的数字
            numbers.remove(index);

            // 更新k值，为下一位计算做准备
            k = k % count;
        }

        return result.toString();
    }
}

